//
//  56. 合并区间.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/21.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution56 {
    // 首先进行按照第一个数进行排序
    // 然后两两进行合并
    // 两两进行合并时，可以采用o(n),也可以采用nlon的时间复杂度
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        let sortedIntervals = intervals.sorted { first, secod in
            return first.first! < secod.first!
        }
        var pre: [Int]?
        var result: [[Int]] = []
        for item in sortedIntervals {
            if pre != nil,item[0] <= pre![1] {
                let merged = [pre![0], max(pre![1], item[1])]
                result.removeLast()
                result.append(merged)
                pre = merged
            } else {
                result.append(item)
                pre = item
            }
        }
        return result
    }
    
    static func test() {
        var intervals = [[1,4],[0,2],[3,5]]
        let solution = Solution56()
        let result = solution.merge(intervals)
        print(result)
    }
}
